Bounded suboptimal search algorithms offer shorter solving times bysacrificing optimality and instead guaranteeing solution costs withina desired factor of optimal. Typically these algorithms use a singleadmissible heuristic both for guiding search and bounding solutioncost. In this paper, we present a new approach to bounded suboptimalsearch, Explicit Estimation Search, that separates these roles,consulting potentially inadmissible information to determine searchorder and using admissible information to guarantee the cost bound.Unlike previous proposals, it successfully combines estimates ofsolution length and solution cost to predict which node will lead mostquickly to a solution within the suboptimality bound. An empiricalevaluation across six diverse benchmark domains shows that ExplicitEstimation Search is competitive with the previous state of the art indomains with unit-cost actions and substantially outperformspreviously proposed techniques for domains in which solution cost andlength can differ.

Heuristic search is a central component of many important applications in AI including automated planning.  While we can find  optimal solutions to heuristic search problems, doing so may take hours or days. For practical applications, this is unacceptably slow, and we must rely on algorithms which find solutions of high, but not optimal, quality or ones which bound the time used directly. In my dissertation, I present and analyze algorithms for the following settings: quality bounded heuristic search and time  bounded heuristic search. The central theme of my doctoral work will be that taking advantage of additional information can improve the performance of heuristic search algorithms.